<!doctype html><html lang=zh-cn dir=ltr>
<head><meta charset=utf-8>
<meta name=viewport content="width=device-width,initial-scale=1"><meta name=description content="本文主要讲的是目前存在的几种缓存算法, 没错, 我又来误人子弟了.
内容会围绕近几年比较流行的LFU, LRU, 还有W-TinyLRU这么三种缓存算法来讲, 尽量使用最简练的文本.
LFU 近期最少使用算法，即LFU算法（Least Frequently Used algorithm）。 这种算法会淘汰近期最少访问的缓存, 仔细分析一下, 没错，这是一种非常合理的算法，因为到目前为止最少使用的页面， 很可能也是将来最少访问的页面。 该算法既充分利用了内存中缓存调度情况的历史信息，又正确反映了程序的局部性。
但是，这种算法的开销极其高, 为了记录每个缓存的使用情况, 你不得不为每一个缓存增加一个很大的计数器, 每次到达临界点, 我们还需要找到所有计数器中最少的缓存, 淘汰它.
核心思想：如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小.  通常我们会这么去实现:
外部结构为Array, 存储元素为KV. K: 该缓存访问次数. V: 缓存本身. 数组按照K排序. 每次缓存大小即将临界, 淘汰K最小的缓存.
顺便一提 Window-LFU 它是LFU算法的改良版. LFU中缓存的访问次数记录的时间范围为整个程序的生命周期, 在Window-LFU中只对特定范围的访问次数进行淘汰. (比如最近10次访问的缓存.)
LRU 最久没有使用算法，即LRU算法（Least Recently Used algorithm）。 这种算法把近期最久没有被访问过的页面作为被替换的页面。 它把LFU算法中要记录数量上的&amp;quot;多&amp;quot;与&amp;quot;少&amp;quot;简化成判断&amp;quot;有&amp;quot;与&amp;quot;无&amp;quot;，因此，实现起来比较容易。
核心思想：如果在一段时间内长时间不访问的页面将来也不会访问.  实现很简单:
假设我们的缓存容量大小为2, 最多缓存2个元素. 下面是缓存的访问顺序.
 1 2 2 3
  第一次: [1]
  第二次: [2, 1]
  第三次: [2, 1]"><title>Cache Algorithm</title><link rel=canonical href=https://sdttttt.github.io/blog/cache-algorithm/>
<link rel=stylesheet href=/scss/style.min.b80bf249ce4a22cf55e8d7340a0b37a2f2c10f54f3a9a49cb94b694a2eb0bbea.css><meta property="og:title" content="Cache Algorithm">
<meta property="og:description" content="本文主要讲的是目前存在的几种缓存算法, 没错, 我又来误人子弟了.
内容会围绕近几年比较流行的LFU, LRU, 还有W-TinyLRU这么三种缓存算法来讲, 尽量使用最简练的文本.
LFU 近期最少使用算法，即LFU算法（Least Frequently Used algorithm）。 这种算法会淘汰近期最少访问的缓存, 仔细分析一下, 没错，这是一种非常合理的算法，因为到目前为止最少使用的页面， 很可能也是将来最少访问的页面。 该算法既充分利用了内存中缓存调度情况的历史信息，又正确反映了程序的局部性。
但是，这种算法的开销极其高, 为了记录每个缓存的使用情况, 你不得不为每一个缓存增加一个很大的计数器, 每次到达临界点, 我们还需要找到所有计数器中最少的缓存, 淘汰它.
核心思想：如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小.  通常我们会这么去实现:
外部结构为Array, 存储元素为KV. K: 该缓存访问次数. V: 缓存本身. 数组按照K排序. 每次缓存大小即将临界, 淘汰K最小的缓存.
顺便一提 Window-LFU 它是LFU算法的改良版. LFU中缓存的访问次数记录的时间范围为整个程序的生命周期, 在Window-LFU中只对特定范围的访问次数进行淘汰. (比如最近10次访问的缓存.)
LRU 最久没有使用算法，即LRU算法（Least Recently Used algorithm）。 这种算法把近期最久没有被访问过的页面作为被替换的页面。 它把LFU算法中要记录数量上的&amp;quot;多&amp;quot;与&amp;quot;少&amp;quot;简化成判断&amp;quot;有&amp;quot;与&amp;quot;无&amp;quot;，因此，实现起来比较容易。
核心思想：如果在一段时间内长时间不访问的页面将来也不会访问.  实现很简单:
假设我们的缓存容量大小为2, 最多缓存2个元素. 下面是缓存的访问顺序.
 1 2 2 3
  第一次: [1]
  第二次: [2, 1]
  第三次: [2, 1]">
<meta property="og:url" content="https://sdttttt.github.io/blog/cache-algorithm/">
<meta property="og:site_name" content="SDTTTTT">
<meta property="og:type" content="article"><meta property="article:section" content="Blog"><meta property="article:tag" content="Algorithm"><meta property="article:published_time" content="2020-10-26T11:03:33+08:00"><meta property="article:modified_time" content="2020-10-26T11:57:13+08:00">
<meta name=twitter:title content="Cache Algorithm">
<meta name=twitter:description content="本文主要讲的是目前存在的几种缓存算法, 没错, 我又来误人子弟了.
内容会围绕近几年比较流行的LFU, LRU, 还有W-TinyLRU这么三种缓存算法来讲, 尽量使用最简练的文本.
LFU 近期最少使用算法，即LFU算法（Least Frequently Used algorithm）。 这种算法会淘汰近期最少访问的缓存, 仔细分析一下, 没错，这是一种非常合理的算法，因为到目前为止最少使用的页面， 很可能也是将来最少访问的页面。 该算法既充分利用了内存中缓存调度情况的历史信息，又正确反映了程序的局部性。
但是，这种算法的开销极其高, 为了记录每个缓存的使用情况, 你不得不为每一个缓存增加一个很大的计数器, 每次到达临界点, 我们还需要找到所有计数器中最少的缓存, 淘汰它.
核心思想：如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小.  通常我们会这么去实现:
外部结构为Array, 存储元素为KV. K: 该缓存访问次数. V: 缓存本身. 数组按照K排序. 每次缓存大小即将临界, 淘汰K最小的缓存.
顺便一提 Window-LFU 它是LFU算法的改良版. LFU中缓存的访问次数记录的时间范围为整个程序的生命周期, 在Window-LFU中只对特定范围的访问次数进行淘汰. (比如最近10次访问的缓存.)
LRU 最久没有使用算法，即LRU算法（Least Recently Used algorithm）。 这种算法把近期最久没有被访问过的页面作为被替换的页面。 它把LFU算法中要记录数量上的&amp;quot;多&amp;quot;与&amp;quot;少&amp;quot;简化成判断&amp;quot;有&amp;quot;与&amp;quot;无&amp;quot;，因此，实现起来比较容易。
核心思想：如果在一段时间内长时间不访问的页面将来也不会访问.  实现很简单:
假设我们的缓存容量大小为2, 最多缓存2个元素. 下面是缓存的访问顺序.
 1 2 2 3
  第一次: [1]
  第二次: [2, 1]
  第三次: [2, 1]">
</head><body class=article-page>
<script>(function(){const e="StackColorScheme";localStorage.getItem(e)||localStorage.setItem(e,"auto")})()</script><script>(function(){const t="StackColorScheme",e=localStorage.getItem(t),n=window.matchMedia("(prefers-color-scheme: dark)").matches===!0;e=="dark"||e==="auto"&&n?document.documentElement.dataset.scheme="dark":document.documentElement.dataset.scheme="light"})()</script>
<div class="container main-container flex on-phone--column compact"><aside class="sidebar left-sidebar sticky">
<button class="hamburger hamburger--spin" type=button id=toggle-menu aria-label="Toggle Menu">
<span class=hamburger-box>
<span class=hamburger-inner></span>
</span>
</button>
<header>
<figure class=site-avatar>
<a href=/>
<img src=/img/avatar_hu8e30117ca872857dd9f41f234a693048_441529_300x0_resize_box_3.png width=300 height=300 class=site-logo loading=lazy alt=Avatar>
</a>
</figure><div class=site-meta>
<h1 class=site-name><a href=/>SDTTTTT</a></h1><h2 class=site-description>臭鱼烂虾</h2></div></header><ol class=menu id=main-menu>
<div class=menu-bottom-section>
<li id=dark-mode-toggle><svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-toggle-left" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentcolor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z"/><circle cx="8" cy="12" r="2"/><rect x="2" y="6" width="20" height="12" rx="6"/></svg><svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-toggle-right" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentcolor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z"/><circle cx="16" cy="12" r="2"/><rect x="2" y="6" width="20" height="12" rx="6"/></svg>
<span>Dark Mode</span>
</li></div></ol></aside><main class="main full-width">
<article class=main-article>
<header class=article-header>
<div class=article-details>
<div class=article-title-wrapper>
<h2 class=article-title>
<a href=/blog/cache-algorithm/>Cache Algorithm</a>
</h2></div><footer class=article-time>
<div><svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-calendar-time" width="56" height="56" viewBox="0 0 24 24" stroke-width="2" stroke="currentcolor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z"/><path d="M11.795 21H5a2 2 0 01-2-2V7a2 2 0 012-2h12a2 2 0 012 2v4"/><circle cx="18" cy="18" r="4"/><path d="M15 3v4"/><path d="M7 3v4"/><path d="M3 11h16"/><path d="M18 16.496V18l1 1"/></svg>
<time class=article-time--published>Oct 26, 2020</time>
</div><div><svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-clock" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentcolor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z"/><circle cx="12" cy="12" r="9"/><polyline points="12 7 12 12 15 15"/></svg>
<time class=article-time--reading>
1 minute read
</time>
</div></footer></div></header><section class=article-content>
<p>本文主要讲的是目前存在的几种缓存算法, 没错, 我又来<del>误人子弟</del>了.</p><p>内容会围绕近几年比较流行的LFU, LRU, 还有W-TinyLRU这么三种缓存算法来讲, 尽量使用最简练的文本.</p><h2 id=lfu>LFU</h2><p>近期最少使用算法，即LFU算法（Least Frequently Used algorithm）。
这种算法会淘汰近期最少访问的缓存,
仔细分析一下, 没错，这是一种非常合理的算法，因为到目前为止最少使用的页面，
很可能也是将来最少访问的页面。
该算法既充分利用了内存中缓存调度情况的历史信息，又正确反映了程序的局部性。</p><p>但是，这种算法的开销极其高, 为了记录每个缓存的使用情况, 你不得不为每一个缓存增加一个很大的计数器,
每次到达临界点, 我们还需要找到所有计数器中最少的缓存, 淘汰它.</p><pre><code>核心思想：如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小.
</code></pre><p>通常我们会这么去实现:</p><p>外部结构为<code>Array</code>, 存储元素为<code>KV</code>. <code>K</code>: 该缓存访问次数. <code>V</code>: 缓存本身.
数组按照K排序. 每次缓存大小即将临界, 淘汰<code>K</code>最小的缓存.</p><p>顺便一提 <code>Window-LFU</code> 它是LFU算法的改良版. LFU中缓存的访问次数记录的时间范围为整个程序的生命周期,
在<code>Window-LFU</code>中只对特定范围的访问次数进行淘汰. (比如最近10次访问的缓存.)</p><h2 id=lru>LRU</h2><p>最久没有使用算法，即LRU算法（Least Recently Used algorithm）。
这种算法把近期最久没有被访问过的页面作为被替换的页面。
它把LFU算法中要记录数量上的"多"与"少"简化成判断"有"与"无"，因此，实现起来比较容易。</p><pre><code>核心思想：如果在一段时间内长时间不访问的页面将来也不会访问.
</code></pre><p>实现很简单:</p><p>假设我们的缓存容量大小为2, 最多缓存2个元素.
下面是缓存的访问顺序.</p><blockquote>
<p>1 2 2 3</p></blockquote><blockquote>
<p>第一次: [1]</p></blockquote><blockquote>
<p>第二次: [2, 1]</p></blockquote><blockquote>
<p>第三次: [2, 1]</p></blockquote><blockquote>
<p>第四次: [3, 2]</p></blockquote><p>最新访问的缓存会放在首位, 很久没有访问的缓存自然而然的就到了末尾, 然后被淘汰.</p><h2 id=w-tinylru>W-TinyLRU</h2><p>知名缓存框架 caffeine 就是使用的这种算法 这种算法结合LRU和LFU算法，解决了突发流量问题带来的。</p><pre><code>整个算法数据结构分成三个段,分别为  Eden,Probation,Protected 三个队列
</code></pre><ul>
<li>
<p>Eden队列: 在caffeine中规定只能为缓存容量的%1,如果size=100,
那这个队列的有效大小就等于1。这个队列中记录的是新到的数据，
防止突发流量由于之前没有访问频率，而导致被淘汰。
比如有一部新剧上线，在最开始其实是没有访问频率的，
防止上线之后被其他缓存淘汰出去，而加入这个区域。</p></li><li>
<p>Probation队列:叫做缓刑队列，在这个队列就代表你的数据相对比较冷，马上就要被淘汰了。<br>
这个有效大小为size减去eden减去protected。</p></li><li>
<p>Protected队列:在这个队列中，可以稍微放心一下了，你暂时不会被淘汰，
但是别急，如果Probation队列没有数据了或者Protected数据满了，
你也将会被面临淘汰的尴尬局面。当然想要变成这个队列，
需要把Probation访问一次之后，就会提升为Protected队列。
这个有效大小为(size减去eden) X 80% 如果size =100，就会是79。</p></li></ul><p><strong>区域规则:</strong></p><ol>
<li>所有的新数据都会进入Eden。</li><li>Eden满了，淘汰进入Probation。</li><li>如果在Probation中访问了其中某个数据，则这个数据升级为Protected。</li><li>如果Protected满了又会继续降级为Probation。</li></ol><p>Probation的淘汰算法也比较有意思, 取出队尾和队首的元素, 然后让这两皇城PK, 输了就淘汰了.</p><p><strong>皇城PK规则:</strong></p><pre><code>1.如果队尾元素的频度大于队首，那么就直接淘汰队首，

2.当队尾频度小于等于队首，且频度小于5的时候，直接将其淘汰

3.当队尾频度小于等于队首，且频度大于5的时候，通过随机的方式进行淘汰任意一个。(看谁运气好咯)
</code></pre></section><footer class=article-footer>
<section class=article-tags>
<a href=/tags/algorithm/>Algorithm</a>
</section><section class=article-lastmod><svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-clock" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentcolor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z"/><circle cx="12" cy="12" r="9"/><polyline points="12 7 12 12 15 15"/></svg>
<span>
Last updated on Oct 26, 2020 11:57 CST
</span>
</section></footer></article><div id=gitalk-container></div><link rel=stylesheet href=https://cdn.jsdelivr.net/npm/gitalk@1.7.2/dist/gitalk.css>
<script src=https://cdn.jsdelivr.net/npm/gitalk@1.7.2/dist/gitalk.min.js></script>
<script src=https://cdn.jsdelivr.net/npm/blueimp-md5@2.18.0/js/md5.min.js></script>
<script>const gitalk=new Gitalk({clientID:"97eb9ce8ac126f0c7833",clientSecret:"5da440441b500b0b016928640712a1b1a03a5f8f",repo:"sdttttt/sdttttt.github.io",owner:"sdttttt",admin:["sdttttt"],distractionFreeMode:!1,id:md5(location.pathname)});(function(){if(["localhost","127.0.0.1"].indexOf(window.location.hostname)!=-1){document.getElementById("gitalk-container").innerHTML="Gitalk comments not available by default when the website is previewed locally.";return}gitalk.render("gitalk-container")})()</script>
<footer class=site-footer>
<section class=copyright>
&copy;
2022 SDTTTTT
</section><section class=powerby>
Built with <a href=https://gohugo.io/ target=_blank rel=noopener>Hugo</a> <br>
Theme <b><a href=https://github.com/CaiJimmy/hugo-theme-stack target=_blank rel=noopener data-version=3.10.0>Stack</a></b> designed by <a href=https://jimmycai.com target=_blank rel=noopener>Jimmy</a>
</section></footer><div class=pswp tabindex=-1 role=dialog aria-hidden=true>
<div class=pswp__bg></div><div class=pswp__scroll-wrap>
<div class=pswp__container>
<div class=pswp__item></div><div class=pswp__item></div><div class=pswp__item></div></div><div class="pswp__ui pswp__ui--hidden">
<div class=pswp__top-bar>
<div class=pswp__counter></div><button class="pswp__button pswp__button--close" title="Close (Esc)"></button>
<button class="pswp__button pswp__button--share" title=Share></button>
<button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>
<button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>
<div class=pswp__preloader>
<div class=pswp__preloader__icn>
<div class=pswp__preloader__cut>
<div class=pswp__preloader__donut></div></div></div></div></div><div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
<div class=pswp__share-tooltip></div></div><button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
</button>
<button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
</button>
<div class=pswp__caption>
<div class=pswp__caption__center></div></div></div></div></div><script src=https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.min.js integrity="sha256-ePwmChbbvXbsO02lbM3HoHbSHTHFAeChekF1xKJdleo=" crossorigin=anonymous defer></script><script src=https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe-ui-default.min.js integrity="sha256-UKkzOn/w1mBxRmLLGrSeyB4e1xbrp4xylgAWb3M42pU=" crossorigin=anonymous defer></script><link rel=stylesheet href=https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/default-skin/default-skin.css integrity="sha256-c0uckgykQ9v5k+IqViZOZKc47Jn7KQil4/MP3ySA3F8=" crossorigin=anonymous><link rel=stylesheet href=https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.css integrity="sha256-SBLU4vv6CA6lHsZ1XyTdhyjJxCjPif/TRkjnsyGAGnE=" crossorigin=anonymous>
</main></div><script src=https://cdn.jsdelivr.net/npm/node-vibrant@3.1.5/dist/vibrant.min.js integrity="sha256-5NovOZc4iwiAWTYIFiIM7DxKUXKWvpVEuMEPLzcm5/g=" crossorigin=anonymous></script><script type=text/javascript src=/ts/main.js defer></script>
<script>(function(){const e=document.createElement("link");e.href="https://fonts.googleapis.com/css2?family=Lato:wght@300;400;700&display=swap",e.type="text/css",e.rel="stylesheet",document.head.appendChild(e)})()</script>
</body></html>